#include "Tree.h"

//树的子结构
//给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
class Solution {
public:
    bool match(TreeNode* p, TreeNode* q)
    {
        if (p == NULL) return q == NULL; //p为空时，q为空，则为其子树
        if (q == NULL) return true;
        if (p->val != q->val) return false;
        return  match(p->left, q->left) && match(p->right, q->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (A == NULL || B == NULL) return false;
        if (A->val == B->val && match(A, B)) return  true;

        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};


//上下区别：上面的 q 为空就一定成立
// 下面的必须两者都为空


//判断另一棵树的子树
//二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
class Solution {
public:
    bool match(TreeNode* p, TreeNode* q)
    {
        if (p == NULL && q == NULL) return true;
        else if (p == NULL || q == NULL) return false;
        if (p->val != q->val) return false;
        return  match(p->left, q->left) && match(p->right, q->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) { //subRoot不为空
        if (root == NULL) return false;
        if (root->val == subRoot->val && match(root, subRoot)) return true;
        return isSubtree(root->left, subRoot) ||
            isSubtree(root->right, subRoot);
    }
};


